package com.LeeCode;

/**
 * 设计链表
 */

public class Code707 {
    public static void main(String[] args) {
        MyLinkedList myLinkedList = new Code707().new MyLinkedList();
        myLinkedList.addAtHead(7);
        myLinkedList.addAtHead(2);
        myLinkedList.addAtHead(1);
        myLinkedList.addAtIndex(3, 0);
        myLinkedList.deleteAtIndex(2);
        myLinkedList.addAtHead(6);
        myLinkedList.addAtTail(4);
        System.out.println(myLinkedList.get(4));
        myLinkedList.addAtHead(4);
        myLinkedList.addAtIndex(5, 0);
        myLinkedList.addAtHead(6);

    }

    class MyLinkedList {
        private ListNode dummyHead;
        private ListNode tail;
        private int size;

        public MyLinkedList() {
            dummyHead = new ListNode(0, null);
            tail = dummyHead;
            size = 0;
        }

        public int get(int index) {
            if (index + 1 <= 0 || index >= size) {
                return -1;
            }
            if (index == size - 1)
                return tail.val;

            ListNode cur = dummyHead;
            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }

        public void addAtHead(int val) {
            ListNode node = new ListNode(val);
            node.next = dummyHead.next;
            dummyHead.next = node;
            if (tail == dummyHead) {
                tail = node;
            }
            size++;
        }

        public void addAtTail(int val) {
            ListNode node = new ListNode(val);
            tail.next = node;
            tail = node;
            size++;
        }

        public void addAtIndex(int index, int val) {
            if (index < 0 || index > size) {
                return;
            }
            if (index == 0) {
                addAtHead(val);
            } else if (index == size) {
                addAtTail(val);
            } else {
                ListNode node = new ListNode(val);
                ListNode pre = dummyHead;
                for (int i = 0; i < index; i++) {
                    pre = pre.next;
                }
                node.next = pre.next;
                pre.next = node;
                size++;
            }
        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index >= size) {
                return;
            }

            ListNode pre = dummyHead;
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }

            pre.next = pre.next.next;
            if (index == size - 1) {
                tail = pre;
            }
            size--;
        }
    }
}
